package com.leetcode.math;

/**
 * @author Dennis Li
 * @date 2020/7/29 21:38
 */
public class CountPrimes_204 {

    public static int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (notPrime[i]) {
                continue;
            }
            count++;
            // 从 i * i 开始，因为如果 k < i，那么 k * i 在之前就已经被去除过了
            // + i 代表质数的k倍
            for (long j = (long) (i) * i; j < n; j += i) {
                notPrime[(int) j] = true;
            }
        }
        return count;
    }

    public boolean isPrime(int num){
        // 只需要判断sqrt(num)是否为质数
        // sqrt(num) 是其分界点
        // 例如12 = 6 * 2 ；当 12 对6 进行判断时，其实在之前就已经通过对2判断实现了
        for (int i = 2; i * i < num; i++) {
            if(num % i == 0) return false;
        }
        return true;
    }

}
